package 图;


import 栈和队列.LLQueue;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Description:
 * @Author: ywk
 * @Date: 2019/12/10 0010 21:49
 */
public class BFSGraph {
    class Vertex {
        public char label;
        public boolean visited;

        public Vertex(char label) {
            this.label = label;
            visited = false;

        }
    }

    class Graph {
        private final int maxVertices = 20;
        private final Vertex[] vertexList;
        private int vertexCount;
        private final int[][] adjMatrix;
        private final Queue<Integer> theQueue;

        public Graph() {
            vertexList = new Vertex[maxVertices];
            adjMatrix = new int[maxVertices][maxVertices];
            vertexCount = 0;
            for (int y = 0; y < maxVertices; y++) {
                for (int x = 0; x < maxVertices; x++) {
                    adjMatrix[x][y] = 0;
                }
            }
            theQueue = new LinkedList<>();
        }

        public void addVertex(char lab) {
            vertexList[vertexCount++] = new Vertex(lab);
        }

        public void addEdge(int start, int end) {

            adjMatrix[start][end] = 1;
            adjMatrix[end][start] = 1;
        }

        public void displayVertex(int v) {
            System.out.println(vertexList[v].label);
        }

        public void bfs() {
            for (int j = 0; j < vertexCount; j++) {
                vertexList[j].visited = false;
            }
            vertexList[0].visited=true;
            displayVertex(0);
            theQueue.add(0);
            int v2;
            while (!theQueue.isEmpty()) {

                Integer v1 = theQueue.remove();

                while ((v2 = getAdjUnvisitedVeterx(v1)) != -1) {
                    vertexList[v2].visited = true;
                    displayVertex(v2);
                    theQueue.add(v2);
                }

            }


        }

        private int getAdjUnvisitedVeterx(int v) {
            for (int j = 0; j < vertexCount; j++) {
                if (adjMatrix[v][j] == 1 && vertexList[j].visited == false) {
                    return j;
                }
            }
            return -1;
        }


    }

}
